https://introtcs.org/public/lec_02_representation.html

개요

The main takeaways from this chapter are:

• We can represent all kinds of objects we want to use as inputs and outputs using binary strings. For example, we can use the binary basis to represent integers and rational numbers as binary strings (see Section 2.1.1 and Section 2.2).
• We can compose the representations of simple objects to represent more complex objects. In this way, we can represent lists of integers or rational numbers, and use that to represent objects such as matrices, images, and graphs. Prefix-free encoding is one way to achieve such a composition (see Section 2.5.2).
• A computational task specifies a map from an input to an output— a function. It is crucially important to distinguish between the “what” and the “how”, or the specification and implementation (see Section 2.6.1). A function simply defines which output corresponds to which input. It does not specify how to compute the output from the input, and as we’ve seen in the context of multiplication, there can be more than one way to compute the same function.
• While the set of all possible binary strings is infinite, it still cannot represent everything. In particular, there is no representation of the real numbers (with absolute accuracy) as binary strings. This result is also known as “Cantor’s Theorem” (see Section 2.4) and is typically referred to as the result that the “reals are uncountable.” It is also implied that there are different levels of infinity though we will not get into this topic in this book (see Remark 2.10).

The two “big ideas” we discuss are Big Idea 1 - we can compose representations for simple objects to represent more complex objects and Big Idea 2 - it is crucial to distinguish between functions’ (“what”) and programs’ (“how”). The latter will be a theme we will come back to time and again in this book.

이번 장에서는 이 네 가지에 대해서 배운다고 한다.

- '모든 종류'의 자료를 binary strings("01110001110")로 표현이 가능하다는 사실.
- prefix-free encoding이라는 방법을 통해 복잡한 자료를 포현한다는 사실. (복잡한걸 이진법으로 표현할 수 있는 더 단순한 것들의 묶음으로 표현)
- 컴퓨터가 하는일은 함수다. 입력 -> 출력을 맵핑하는 일. 
- 이진법의 조합은 무한하지만, 그럼에도 불구하고 세상의 모든것을 표현할 수는 없다는 사실. (칸토어의 이론)

이진수로 표현하기

"표현"

우리가 컴퓨터에 사진, 음악, 영상 등 데이터를 저장할 때 진짜로 저장되는 것은 그것들의 '표현'이다. 우리의 뇌 마저도 감각된 그 자체가 입력되지 않고 그것의 표현을 저장한다.
컴퓨터는 0과 1로 된 binary strings밖에 저장하지 못하니까 결국 모든걸 0과 1로 번역하고 그걸 저장한다.

그래서 중요한건 "어떻게"의 문제다. representation scheme.
자연수, 소수, 문자열, 이미지, 영상 등등 모든걸 어떻게 0과1로 만들것인가?

자연수

자연수를 이진법으로 표현하는 방법은 매우 익숙하다.
이걸 파이썬으로 표현하면 이렇다.

def NtS(n):# natural numbers to strings
if n > 1:
return NtS(n // 2) + str(n % 2)
else:
return str(n % 2)
print(NtS(236))
# 11101100
print(NtS(19))
# 10011

​해당 숫자를 2로 나눈 나머지 (0 or 1)을 기입.
그리고 다시 그 숫자를 2로 나눈뒤에 반복.
언제까지? n이 2 미만일 때 까지.

음수

위의 NtS()결과 앞에 양수라면 0을 음수라면 1을 추가한다.
이건 과거의 방법이고 요즘의 방법은 밑에서 서술.

어떻게 구별하나?

위에서도 보면 NtS(19)의 결과물은 10011인데, 19는 양수가 아닌가?
맨 앞에 있는게 음수와 양수를 구별하는 용도로 추가한 비트인지 아닌지 어떻게 알까?
그러면 더 근본적인 질문으로 넘어가게 된다.
10011010101 이렇게 있는게 애초에 숫자인걸 우리는 어떻게 알까?
간단히 대답하자면 그럴 필요가 없다. 컴파일러가 해당 자료의 자료형을 미리 정하기 때문에.
똑같은 1110101이라도 그게 int인지 string인지 아니면 혹은 다른 무엇가인지에 따라 다르게 해석된다는것이다.

Two's complement representation

여기서는 정확히 요즘은 어떻게 음수를 표현하는지에 대해 알려준다.
4비트 표현법에서 -8을 나타내보자.
$n=4-1 , ZtS_{3}(−8)=NtS_4(2^4−8)=1000$
그럼 4비트에서 16은 어떻게 나타낼까?
$NtS(16)=10000$ 인데 여기서 앞의 4자리만 가져오니까 0000이다.
그래서 4비트표현법 안에서 1000은 16이 아니라 -8이 된다.
결과적으로는 과거의 sign bit 방식과 같다. 앞이 1이면 음수 0이면 양수.

유리수

-5/8 이라는 유리수를 어떻게 표현할까.
-5 -> 1101, 8->01000 하면 (1101,01000) 두 이진수가 나온다.
이걸 각 숫자를 두번씩 반복한다. 0은 00으로 1은 11로.
11110011,0011000000 이 되고 그 둘 사이에 01을 넣고 있는다.
11110011 01 0011000000(구별하기 쉽게 스페이스를 넣음) = -5/8

실수(부동소수점 표기)

어떤 실수 x가 있으면 x와 근접한 $b * 2^e$ 를 찾아서 (b,e) 쌍으로 표현한다.
12.75 은 이렇게 이진수로 변환된다.

1. 이진법 변환
   12는 이진수로 1100
   $0.75 = 0.5 + 0.25 = 1/2 + 1/2^2 = 0.11$ 둘을 합쳐서 1100.11

2. Scientific notation
   1100.11이란 숫자를 앞에 한 자리만 남기도록 소수점을 옮기면
   1.10011이 되고 소수점은 3자리를 옮겼으니 $1.10011 * 2^3$ 이라고 표기.

3. 각 부분 구하기
   부호: 12.75는 양수니까 sign bit은 0.
   지수: 3 + 127 = 130 = 10000010
   가수: 10011 (위의 2단계 숫자에서 소수점 뒤 부분만 가져오고 나머지는 0으로)
   12.75 = 0 100000010 10011000000000000000000

12.3 처럼 딱 떨어지지 않는 실수는?
12 -> 1100은 동일.
0.3은 어떻게 구하나?
0.3 를 2씩 곱하면서 소수점 앞에 숫자를 적고 버린다.
0.3 * 2 = 0.6 -> 0
0.6 * 2 = 1.2 -> 1
0.2 * 2 = 0.4 -> 0
0.4 * 2 = 0.8 -> 0
0.8 * 2 = 1.6 -> 1
이렇게 무한히 가다가 정해진 자릿수에서 멈춘다.(보통은 23비트. 왜냐하면 float 32비트에서 부호 1비트, 지수 8비트 를 빼면 23비트만 남기 때문에)
그래서 1100.01001.......0 까지 구한다음에 그걸
정규화를 거쳐 1.10001001......0 * 2^3
그래서 12.3 = 0 10000010 10001001100110011001101